During the past fifty years, the electronics and computing industries have been relentlessly propelled forward by the ever decreasing sizes of basic electronic components, such as transistors and signal lines, and by the correspondingly ever increasing component densities of integrated circuits, including processors and electronic memory chips. Eventually, however, it is expected that fundamental component-size limits will be reached in semiconductor-circuit-fabrication technologies based on photolithographic methods. As the size of components decreases below the resolution limit of ultraviolet light, for example, far more technically demanding and expensive higher-energy-radiation-based technologies need to be employed to create smaller components using photolithographic techniques. Not only must expensive semiconductor fabrication facilities be rebuilt in order to use the new techniques, many new obstacles are expected to be encountered. For example, it is necessary to construct semiconductor devices through a series of photolithographic steps, with precise alignment of the masks used in each step with respect to the components already fabricated on the surface of a nascent semiconductor. As the component sizes decrease, precise alignment becomes more and more difficult and expensive. As another example, the probabilities that certain types of randomly distributed defects in semiconductor surfaces result in defective semiconductor devices may increase as the sizes of components manufactured on the semiconductor services decrease, resulting in an increasing proportion of defective devices during manufacture, and a correspondingly lower yield of useful product. Ultimately, various quantum effects that arise only at molecular-scale distances may altogether overwhelm current approaches to component construction in semiconductors.
In view of these problems, researchers and developers have expended considerable research effort in fabricating microscale and nanoscale electronic devices using alternative technologies, where nanoscale electronic devices generally employ nanoscale signal lines having widths, and nanoscale components having dimensions, of less than 100 nanometers. More densely fabricated nanoscale electronic devices may employ nanoscale signal lines having widths, and nanoscale components having dimensions, of less than 50 nanometers.
Although general nanowire technologies have been developed, it is not necessarily straightforward to employ nanowire technologies to miniaturize existing types of circuits and structures. While it may be possible to tediously construct miniaturized, nanowire circuits similar to the much larger, current circuits, it is impractical, and often impossible, to manufacture such miniaturized circuits. Even were such straightforwardly miniaturized circuits able to feasibly manufactured, the much higher component densities that ensue from combining together nanoscale components necessitate much different strategies related to removing waste heat produced by the circuits In addition, the electronic properties of substances may change dramatically at nanoscale dimensions, so that different types of approaches and substances may need to be employed for fabricating even relatively simple, well-known circuits and subsystems at nanoscale dimensions. Thus, new implementation strategies and techniques need to be employed to develop and manufacture useful circuits and structures at nanoscale dimensions using nanowires.
One type of circuit that would be desirable to produce at nanoscale dimensions is an associative array. Associative arrays find widespread use in computers and other electronic devices. An associative array may be implemented either in software or hardware, and hardware-implemented associative arrays are particularly useful for implementing complex logic circuitry requiring retrieval of values paired with keys, including routers and complex computer systems. FIG. 1 shows an exemplary hardware-implemented associative array. The associative array 102 internally stores a table 104 of key/value pairs. The keys may be of arbitrary size, and the corresponding values may also be of arbitrary size. Each key/value pair is stored in a row, such as row 106, of the key/value-pair table 104. In FIG. 1, the successive rows of the table are assigned monotonically increasing addresses, from 0 to 7. The associative array 102 receives, in FIG. 1, three pairs of key input lines 108, 110, and 112, each key-input-line pair comprising a key line and its complement. For example, key-line pair 108 includes the key line k1 113 and its complement {overscore (k)}1 113. Each key-input-line pair represents a single bit of a key. Thus, in the exemplary associative array shown in FIG. 1, keys comprise three bits, which specify a range of values between 0 and 7. Note, however, that the keys have no correspondence with key/value-pair-table row addresses. The associative array 102 in FIG. 1 outputs 9 output signal lines, including 8 value output signal lines 116-123 and a valid-bit output signal line 124.
FIGS. 2 and 3 illustrate operation of the associative array shown in FIG. 1. When a particular key, such as the key “keyb” 202, is input to the key input signal lines 108, 110, and 112, and when the key/value-pair table 104 contains the input key, then the value portion of the key/value pair with key equal to the input key is output to the value output signal lines 116-123 and an ON, or “1, ” value is output to the valid-bit output signal line 124. In FIG. 2, key “keyb” is contained in the second row 204 of the key/value-pair table 104. Therefore, the associative array 102 outputs the value “value1” in response to input of key “keyb.” Thus, an associative array matches input keys to stored key/value pairs, and when a key/value pair is found within the associative array with a key equal to the input key, the value portion of the key/value pair is output, along with an indication that the input key was found in the associative array, encoded in output of an ON or “1” value to the valid-bit output signal line 124. As shown in FIG. 3, when an input key, such as the key “keyx” 302, is not found within the key/value-pair table 104, then the output value is undefined, and the lack of a match of the input key with stored keys is indicated by output of an OFF or “0” state to the valid-bit output signal line 124.
Associative arrays find frequent use in circuitry supporting operating systems, network routers, and other such electronic devices and computer systems. Designers, manufacturers, and users of these systems have recognized the need for ever-smaller associative memories compatible with the ever-decreasing electrical component sizes in modern electronic devices. For this reason, a need has been recognized for nanoscale associative memories. Unfortunately, the current methods by which associative arrays are fabricated are not amenable to simple miniaturization using nanowire-based structures similar to those currently employed at larger dimensions. Instead, designers, manufacturers, and users of devices that include associative arrays have recognized the need for new methods for implementing associative arrays that are useable at nanoscale dimensions. Moreover, to facilitate reuse and flexibility of associative-array components, designers, manufacturers, and users of devices that include associative arrays have recognized the need for reprogrammable associative arrays that can be reconfigured for alternative uses or to enhance the devices in which they are included.